package cn.bellychang.leetcode.question125;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.
 *
 * Note: For the purpose of this problem, we define empty string as valid palindrome.
 *
 * s consists only of printable ASCII characters.
 *
 * @author ChangLiang
 * @date 2021/1/29
 */
public class Solution2 {

    public boolean isPalindrome(String s) {

        Deque<Character> dequeA = new ArrayDeque<>(s.length());
        Deque<Character> dequeB = new ArrayDeque<>(s.length());

        char[] chars = s.toLowerCase().toCharArray();
        for (char aChar : chars) {
            if (isAlphanumeric(aChar)) {
                dequeA.push(aChar);
            }
        }
        for (int i = s.length()-1; i >=0; i--) {
            if (isAlphanumeric(chars[i])) {
                dequeB.push(chars[i]);
            }
        }

        for (int i = 0; i< dequeA.size(); i++) {
            char popA = dequeA.pop();
            char popB = dequeB.pop();
            if (popA != popB) {
                return false;
            }
        }
        return true;
    }

    private boolean isAlphanumeric(char aChar) {
        return (aChar >= 'a' && aChar <= 'z') || (aChar >= '0' && aChar <= '9');
    }
}
